/// @tags: ConvexOptimization
#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

namespace BlueQuantum {

int const N = 1e5 + 5;

int n, m, need;
int sum, temp;
int cnt;
int fa[N];

struct Node {
  int u, v, w, c;
  inline bool operator<(Node const &rhs) const {
    return w == rhs.w ? c > rhs.c : w < rhs.w;
  }
} e[N];

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

inline void kruskal() {
  for (int i = 0; i < n; ++i) fa[i] = i;
  sum = cnt = temp = 0;
  sort(e + 1, e + m + 1);
  for (int i = 1; cnt != n - 1; ++i) {
    int u = find(e[i].u), v = find(e[i].v);
    if (u != v) {
      cnt++;
      fa[u] = v;
      if (e[i].c == 0) temp++;
      sum += e[i].w;
    }
  }
}

inline int main() {
  cin >> n >> m >> need;
  for (int i = 1; i <= m; ++i) cin >> e[i].u >> e[i].v >> e[i].w >> e[i].c;
  int l = -1e2 - 5, r = 1e2 + 5;
  while (l < r) {
    int mid = (l + r + 1) >> 1;
    for (int i = 1; i <= m; ++i)
      if (e[i].c == 0) e[i].w -= mid;
    kruskal();
    temp <= need ? l = mid : r = mid - 1;
    for (int i = 1; i <= m; ++i)
      if (e[i].c == 0) e[i].w += mid;
  }
  for (int i = 1; i <= m; ++i)
    if (e[i].c == 0) e[i].w -= l;
  kruskal();
  cout << sum + need * l << '\n';
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P2619 [国家集训队] Tree I.in", "r", stdin);
  freopen("P2619 [国家集训队] Tree I.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
